Optimizing a linear function over an integer efficient set

In this paper, a method for optimizing a linear function over the integer Pareto-optimal set without having to determine all integer efficient solutions is presented. The proposed algorithm is based on a simple selection technique that improves the linear objective value at each iteration. Two types of cuts are performed successively until the optimal value is obtained and the current truncated region contains no integer feasible solution.     

Relative gerbes

This paper introduces the notion of “relative gerbes” for smooth maps of manifolds, and discusses their differential geometry. The equivalence classes of relative gerbes are further classified by the relative integral cohomology in degree 3.     

Fluid and diffusion limits for transient sojourn times of processor sharing queues with time varying rates

We provide an approximate analysis of the transient sojourn time for a processor sharing queue with time varying arrival and service rates, where the load can vary over time, including periods of overload. Using the same asymptotic technique as uniform acceleration as demonstrated in [12] and [13], we obtain fluid and diffusion limits for the sojourn time of the M_t/M_t/1 processor-sharing queue. Our analysis is enabled by the introduction of a “virtual customer” which differs from the notion of a “tagged customer” in that the former has no effect on the processing time of the other customers in the system. Our analysis generalizes to non-exponential service and interarrival times, when the fluid and diffusion limits for the queueing process are known.     

Improving Construction for Connected Dominating Set with Steiner Tree in Wireless Sensor Networks

The connected dominating set plays an important role in ad hoc wireless networking. Many constructions for approximating the minimum connected dominating set have been proposed in the literature. In this paper, we propose a new one with Steiner tree, which produces approximation solution within a factor of 6.8 from optimal. This approximation algorithm can also be implemented distributedly.     

A study of predator–prey models with the Beddington–DeAnglis functional response and impulsive effect

In this paper, the predator–prey system with the Beddington–DeAngelis functional response is developed, by introducing a proportional periodic impulsive catching or poisoning for the prey populations and a constant periodic releasing for the predator. The Beddington–DeAngelis functional response is similar to the Holling type II functional response but contains an extra term describing mutual interference by predators. This model has the potential to protect predator from extinction, but under some conditions may also lead to extinction of the prey. That is, the system exists a locally stable prey-eradication periodic solution when the impulsive period satisfies an inequality. The condition for permanence is established via the method of comparison involving multiple Liapunov̀ functions. Further, by numerical simulation method the influences of the impulsive perturbations and mutual interference by predators on the inherent oscillation are investigated. With the increasing of releasing for the predator, the system appears a series of complex phenomenon, which include (1) period-doubling, (2) chaos attractor, (3) period-halfing. (4) non-unique dynamics (meaning that several attractors coexist).     

Tree loop graphs

Many problems involving DNA can be modeled by families of intervals. However, traditional interval graphs do not take into account the repeat structure of a DNA molecule. In the simplest case, one repeat with two copies, the underlying line can be seen as folded into a loop. We propose a new definition that respects repeats and define loop graphs as the intersection graphs of arcs of a loop. The class of loop graphs contains the class of interval graphs and the class of circular-arc graphs. Every loop graph has interval number 2. We characterize the trees that are loop graphs. The characterization yields a polynomial-time algorithm which given a tree decides whether it is a loop graph and, in the affirmative case, produces a loop representation for the tree.     

Determining Modes for Continuous Data Assimilation in 2D Turbulence

We study the number of determining modes necessary for continuous data assimilation in the two-dimensional incompressible Navier–Stokes equations. Our focus is on how the spatial structure of the body forcing affects the rate of continuous data assimilation and the number of determining modes. We treat this problem analytically by proving a convergence result depending on the H ^–1 norm of f and computationally by considering a family of forcing functions with identical Grashof numbers that are supported on different annuli in Fourier space. The rate of continuous data assimilation and the number of determining modes is shown to depend strongly on the length scales present in the forcing.     

Exact Solutions of Extended Boussinesq Equations

The problem addressed in this paper is the verification of numerical solutions of nonlinear dispersive wave equations such as Boussinesq-like system of equations. A practical verification tool for numerical results is to compare the numerical solution to an exact solution if available. In this work, we derive some exact solitary wave solutions and several invariants of motion for a wide range of Boussinesq-like equations using Maple software. The exact solitary wave solutions can be used to specify initial data for the incident waves in the Boussinesq numerical model and for the verification of the associated computed solution. The invariants of motions can be used as verification tools for the conservation properties of the numerical model.     

Towards the Exact Minimization of BDDs—An Elitism-Based Distributed Evolutionary Algorithm

Binary Decision Diagrams (BDDs) are the state-of-the-art data structure for representation and manipulation of Boolean functions. In general, exact BDD minimization is NP-complete. For BDD-based technology, a small improvement in the number of nodes often simplifies the follow-up problem tremendously. This paper proposes an elitism-based evolutionary algorithm (EBEA) for BDD minimization. It can efficiently find the optimal orderings of variables for all LGSynth91 benchmark circuits with a known minimum size. Moreover, we develop a distributed model of EBEA, DEBEA, which obtains the best-ever variable orders for almost all benchmarks in the LGSynth91. Experimental results show that DEBEA is able to achieve super-linear performance compared to EBEA for some hard benchmarks.